package com.itheima.leetcode.od.b.stack;

import java.util.Arrays;
import java.util.LinkedList;

/**
 * (B卷,200分)- 荒岛求生（Java & JS & Python & C）
 * <p>
 * 题目描述
 * <p>
 * 一个荒岛上有若干人，岛上只有一条路通往岛屿两端的港口，大家需要逃往两端的港口才可逃生。
 * <p>
 * 假定每个人移动的速度一样，且只可选择向左或向右逃生。
 * <p>
 * 若两个人相遇，则进行决斗，战斗力强的能够活下来，并损失掉与对方相同的战斗力；若战斗力相同，则两人同归于尽。
 * <p>
 * 输入描述
 * <p>
 * 给定一行非 0 整数数组，元素个数不超过30000；
 * <p>
 * 正负表示逃生方向（正表示向右逃生，负表示向左逃生），绝对值表示战斗力，越左边的数字表示里左边港口越近，逃生方向相同的人永远不会发生决斗。
 * <p>
 * 输出描述
 * <p>
 * 能够逃生的人总数，没有人逃生输出0，输入异常时输出-1。
 * <p>
 * 用例
 * <p>
 * 输入	5 10 8 -8 -5
 * 输出	2
 * 说明	第3个人和第4个人同归于尽，第2个人杀死第5个人并剩余5战斗力，第1个人没有遇到敌人。
 * <p>
 * 题目解析
 * <p>
 * 本题可以利用栈结构解题。
 * <p>
 * 解题思路如下：
 * <p>
 * 我们可以假设所有数字都向左逃生，那么从左边出来的只有两种情况：
 * <p>
 * 正数
 * 负数
 * 如果左边出来的是正数，则由于正数不能从左边逃生，而只能从右边出口逃生，因此我们不能算该正数逃生成功，并且该正数还会成为左边出来的负数的逃生阻力，因此我们将左边出来的正数缓存进栈中。
 * <p>
 * 如果左边出来的是负数，则由于负数可以从左边出口逃生，因此此时，我们需要检查栈中有没有缓存的正数（阻力），如果有，则需要将左边逃出来的负数 和 栈顶的正数，进行pk（二者求和）：
 * <p>
 * 假设负数逃生成功个数为negative，正数逃生成功个数为positive
 * <p>
 * 若 pk > 0，则负数逃生失败，栈顶正数减少战斗力后重新入栈
 * 若 pk < 0，则负数打败了栈顶正数，负数减少战斗力，然后继续和新的栈顶正数pk：
 * 若栈已经空了，则此负数逃生成功，我们将负数逃生成功个数negative+1
 * 若栈未空，则继续pk逻辑
 * 若 pk == 0，则负数和栈顶正数同归于尽
 * 按此逻辑，最后栈的大小其实就是逃生成功的正数个数postive，我们只要求和negative+postive即为题解。
 */
public class ChickenDinner {
    public static void main(String[] args) {
        /*Scanner sc = new Scanner(System.in);
        int[] nums = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();*/

        int[] nums = Arrays.stream("5 10 8 -8 -5".split(" ")).mapToInt(Integer::parseInt).toArray();
        System.out.println(getResult(nums));
    }

    public static int getResult(int[] nums) {
        // 负数逃生的总人数
        int negative = 0;

        // 正数缓冲栈，注意该栈只缓存正数
        LinkedList<Integer> positive = new LinkedList<>();

        // 正序遍历nums，遍历出来的num，相当于从左边逃生
        for (int num : nums) {
            // 输入异常时输出-1
            if (num == 0) {
                return -1;
            }

            if (num > 0) {
                // 如果左边逃出来的是正数，则缓冲到栈中
                positive.addLast(num);
            } else {
                // 如果左边逃出来的是负数
                while (true) {
                    if (positive.size() == 0) {
                        // 如果栈为空，即没有正数，此时左边逃出来的负数直接逃生成功
                        negative++;
                        break;
                    }

                    // 如果栈不为空，则栈中有缓冲的正数，此时负数需要和栈顶正数进行pk
                    int pk = num + positive.removeLast();

                    if (pk > 0) {
                        // 如果pk结果大于0，则负数逃生失败，栈顶的正数减少战斗力
                        positive.addLast(pk);
                        break;
                    } else if (pk < 0) {
                        // 如果pk结果小于0，则负数pk成功，此时需要继续和新栈顶正数pk，即进入下一轮
                        num = pk;
                    } else {
                        // 如果pk结果为0，则同归于尽
                        break;
                    }
                }
            }
        }

        // 最终逃生成功的人数：negative即负数逃生成功个数，positive.size()即正数逃生成功个数
        return negative + positive.size();
    }
}